package 算法_递归分治;

import java.util.Arrays;

public class Quick_Sort {
    public static void main(String[] args) {
        int[] a = {2, 1, 4, 6, 3, 6, 8, 9};
        quick_sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void quick_sort(int[] a, int l, int r) {
        int i = l, j = r;
        if (l < r) {
            int x = a[i];
            while (i < j) {
                while (i < j && x < a[j]) j--;
                if (i < j) a[i++] = a[j];
                while (i < j && x > a[i]) i++;
                if (i < j) a[j--] = a[i];
            }
            a[i] = x;
            quick_sort(a, l, i - 1);
            quick_sort(a, i + 1, r);
        }
    }
}
